package com.my.learn.exercise.data.struct.leetcode.difficult;
/*
 * 创建人：baimiao
 * 创建时间：2024/12/19 15:58
 *
 * 214. 最短回文串
 * 给定一个字符串 s，你可以通过在字符串前面添加字符将其转换为
回文串。找到并返回可以用这种方式转换的最短回文串。
示例 1：
输入：s = "aacecaaa"
输出："aaacecaaa"
示例 2：
输入：s = "abcd"
输出："dcbabcd"
提示：

0 <= s.length <= 5 * 104
s 仅由小写英文字母组成
 *
 *
 */

import org.apache.commons.lang3.StringUtils;

public class ShortestPalindromeH214 {


    /***
     *
     *    abbba bb bbbbb
     *
     *
     *    aaaacbdaaaa
     *
     *    abababab abababab
     *
     * */


    // 两组游标分别控制一个固定滑块的值 size = length/2 > 10?10:length/2 ,left1->left2 == right2<-right1,
    //如果小于size,匹配上则left1,right1固定不动，不匹配 right1,right2向左滑动，一直匹配直到left1=right1
    //滑块等于size时 left1,left2,right1,right2同时移动
    //如果匹配 left1，left2 向右移动，right1,right2向左移动
    //如果不匹配，left1=left2回退到0,right2=right1都等于right2的值,相当于令s =s.substring(0,right1+1)
    //重复上述步骤，直到left2=right2
    //
    public static void main(String[] args) {
        ShortestPalindromeH214 palindrome = new ShortestPalindromeH214();
//        String s = "aacecaaa";
        String s = "cacedcac";
//        String s = "aaaaaaaaaaaaa aaaaab ccccccccccccc caaaaa aaaaaaaaaaaaaaaaaaa";
        String result = palindrome.shortestPalindrome(s);
        System.out.println(result);
    }


    public String shortestPalindrome(String s) {
        int length = s.length();
        if (length < 2) {
            return s;
        }
        int pos = compare(s, 29, 10);
        if (pos < length) {
            s = StringUtils.reverse(s.substring(pos)) + s;
        }
        return s;
    }

    private int compare(String s, int base, int size) {
        int length = s.length();
        int left1, left2, right1, right2;
        left1 = left2 = 0;
        right1 = right2 = length - 1;
        int cursor = size;
        long lsm = 0, rsm = 0;
        while (left1 < right1) {
            int lbtm = (int) s.charAt(left2) - 96;
            int rbtm = (int) s.charAt(right2) - 96;
            long lval = lbtm * ((long) Math.pow(base, cursor));
            long rval = rbtm * ((long) Math.pow(base, cursor));
            lsm += lval;
            rsm += rval;
            if (lsm == rsm) {
                if (left2 - left1 <= size) {
                    left2++;
                    right2--;
                    cursor--;
                } else {
                    lsm = (lsm - ((int) s.charAt(left1) - 96) * (long) Math.pow(base, size)) * base;
                    rsm = (rsm - ((int) s.charAt(right1) - 96) * (long) Math.pow(base, size)) * base;
                    left1++;
                    left2++;
                    right2--;
                    right1--;
                }
                if (left2 >= right2) {
                    break;
                }
            } else {
                if (left2 - left1 <= size) {
                    lsm = lsm - lval;
                    rsm = (rsm - ((int) s.charAt(right1) - 96) * (long) Math.pow(base, size)) * base;
                    right1--;
                    right2--;
                } else {
                    s = s.substring(0, right1 + 1);
                    return compare(s, base, size);
                }
            }

        }

        if (right2 == left2) {
            return 2 * left2 + 1;
        } else {
            return 2 * left2 + 2;
        }
    }

}
